package com.fw.leetcode.tree;

import com.fw.leetcode.LeetCode;

/**
 * 236. Lowest Common Ancestor of a Binary Tree
 *
 * Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
 * According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between
 * two nodes p and q as the lowest node in T that has both p and q as descendants
 * (where we allow a node to be a descendant of itself).”
 *
 * Example 1:
 *  Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
 *  Output: 3
 *  Explanation: The LCA of nodes 5 and 1 is 3.
 *
 * Example 2:
 *  Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
 *  Output: 5
 *  Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
 *
 * Example 3:
 *  Input: root = [1,2], p = 1, q = 2
 *  Output: 1
 *
 * Constraints:
 *  The number of nodes in the tree is in the range [2, 10^5].
 *  -10^9 <= Node.val <= 10^9
 *  All Node.val are unique.
 *  p != q
 *  p and q will exist in the tree.
 */
public class Num_0236 implements LeetCode {
    private interface Solution extends Tree {
        TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q);

        default void assertExpected(Integer[] root, int p, int q, int expected) {
            TreeNode rooNode = buildBinaryTree(root);
            if (lowestCommonAncestor(rooNode, new TreeNode(p), new TreeNode(q)).val != expected) {
                lowestCommonAncestor(rooNode, new TreeNode(p), new TreeNode(q));
            }
        }
    }

    private static class MySolution implements Solution {

        @Override
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { // 其次：（常规）深度优先遍历（递归）：时O(n) 空O(log n)
            /*
             * 二叉树最近公共祖先
             * root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1  => 3
             * root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4  => 5
             *                    3
             *           5                  1
             *      6        2         0         8
             *  null null  7   4
             *
             *       root
             *   left   right
             * => is root: if (5,1) in [root left right] 全局只有一个节点满足此条件
             */
            TreeNode header = new TreeNode(); // 辅助节点
            header.left = root; // 根
            header.right = null; // 用于存储结果
            contains(header, root, p, q);
            return header.right;
        }

        /**
         * root 节点之下是否存在 p 或 q
         * @return 1|存在 0|不存在
         */
        private int contains(TreeNode header, TreeNode root, TreeNode p, TreeNode q) {
            if (root == null) return 0;
            int rootCnt = root.val == p.val || root.val == q.val ? 1 : 0;
            int leftCnt = contains(header, root.left, p, q);
            int rightCnt = contains(header, root.right, p, q);
            int totalCnt = rootCnt + leftCnt + rightCnt;
            if (totalCnt >= 2) { // 满足条件时，记录当前节点，并返回 1
                header.right = root;
                return 1; // 注意不能返回 2
            }
            return totalCnt;
        }
    }

    private static class MyOptimizeSolution implements Solution {

        @Override
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { // 最优：（挖掘隐含条件）深度优先遍历（递归）：时O(n) 空O(log n)
            /*
             * 二叉树最近公共祖先
             * root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1  => 3
             * root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4  => 5
             *                    3
             *           5                  1
             *      6        2         0         8
             *  null null  7   4
             *
             * 优化第一种使用 contains 计数的方法
             * 1）同时存在 p 和 q 时，最近公共祖先是 root
             *       root
             *   left   right
             * => is root: if (p,q) in [root left right] 全局只有一个节点满足此条件
             * 2）[隐含] 仅存在一个 p 或 q 时，最近公共祖先是 p 或 q 自身
             * => is p or q
             */
            if (root == null || root.val == p.val || root.val == q.val) {
                return root;
            }
            TreeNode leftAncestor = lowestCommonAncestor(root.left, p, q);
            TreeNode rightAncestor = lowestCommonAncestor(root.right, p, q);
            if (leftAncestor != null && rightAncestor != null) {
                return root;
            }
            return leftAncestor != null ? leftAncestor : rightAncestor;
        }
    }

    public static void main(String[] args) {
        Solution solution = new MyOptimizeSolution();
        solution.assertExpected(new Integer[]{3,5,1,6,2,0,8,null,null,7,4}, 5, 1, 3);
        solution.assertExpected(new Integer[]{3,5,1,6,2,0,8,null,null,7,4}, 5, 4, 5);
        solution.assertExpected(new Integer[]{1,2}, 1, 2, 1);
    }
}
